

 // 力扣86. 分隔链表
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummySmall = new ListNode(0); // 用于存储小于x的节点
        ListNode dummyLarge = new ListNode(0); // 用于存储大于等于x的节点
        ListNode small = dummySmall;
        ListNode large = dummyLarge;
        ListNode curr = head;

        while (curr != null) {
            if (curr.val < x) {
                small.next = curr;
                small = small.next;
            } else {
                large.next = curr;
                large = large.next;
            }
            curr = curr.next;
        }

        // 连接两个链表
        small.next = dummyLarge.next;
        large.next = null; // 防止循环

        return dummySmall.next;
    }
}